//************************************************************
//    > File Name: invert-binary-tree.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月22日 11:07:52
//***********************************************************
//lintcode #175
#include<bits/stdc++.h>
#include<queue>
using namespace std;
class TreeNode{
	public:
		int val;
		TreeNode *left,*right;
		TreeNode(int val=-1){
			this->val=val;
			this->left=this->right=NULL;
		}
};
void invertBinaryTree(TreeNode *root){
	if(root==NULL)
		return;
	TreeNode *t=root->left;
	root->left=root->right;
	root->right = t;
	invertBinaryTree(root->left);
	invertBinaryTree(root->right);
}
void invertBinaryTree2(TreeNode *root){
	if(root!= nullptr){
		queue<TreeNode*> nodes;
		nodes.emplace(root);
		while(!nodes.empty()){
			auto node = nodes.front();
			nodes.pop();
			swap(node->left,node->right);
			if(node->left!=nullptr)
				nodes.emplace(node->left);
			if(node->right!=nullptr)
				nodes.emplace(node->right);
		}
	}

}
int main(){
	TreeNode *t1= new TreeNode[3];
	t1[0].val=1,t1[1].val=2,t1[2].val=3;
	t1[0].left=&t1[1];
	t1[0].right=&t1[2];
	cout<<t1[0].val<<t1[0].left->val<<t1[0].right->val<<endl;

//	invertBinaryTree(t1);
	invertBinaryTree2(t1);
	cout<<t1[0].val<<t1[0].left->val<<t1[0].right->val<<endl;
	delete []t1;
}
